/******************************************************
 *  Project：括号匹配算法实现
 *  Function: 使用栈实现括号匹配
 *  Description:
 *  PROJECT_FILENAME:
 *  Author: coder-itl
 ******************************************************
 *  Copyright 2021/10/17 by coder-itl
 ******************************************************/


#include "stdio.h"

#define MAX_SIZE 255 /* 设栈中元素个数为 255 */
#define TRUE 1
#define FALSE 0
#define missingClosingParenthesis 1 /* 1: 缺少右括号 */
#define missingOpeningParenthesis 2 /* 2: 缺少左括号 */
#define laRParenthesesDOMatch 3 /* 左右括号不匹配 */
#define matchSuccessfully 4 /* 匹配成功 */


typedef char StackElementType;

typedef struct {
    /* 用来存放栈中元素的一维数组 */
    StackElementType elem[MAX_SIZE];
    /* 用来存放栈顶元素的下标,top为 -1表示空栈  */
    int top;
    /* 栈内元素个数 */
    int length;
} SeqStack;


void InitStack(SeqStack *seqStack);

int Push(SeqStack *seqStack, StackElementType element);

int Pop(SeqStack *seqStack, StackElementType *element);

int IsEmptySeqStack(SeqStack *seqStack);

void GetSeqStackTopElement(SeqStack *seqStack, StackElementType *element);

int Match(char ch1, char ch2);

void BracketMatch(char *str);

int main() {
    char str[MAX_SIZE];
    gets(str);
    BracketMatch(str);
    /* TODO: 输入完毕在对 BracketMatch 方法调用 */
    return 0;
}

/**
 * 初始化栈
 * @param seqStack
 */
void InitStack(SeqStack *seqStack) {
    /* 构造一个空栈 */
    seqStack->top = -1;
    seqStack->length = 0;
}

/**
 * 入栈操作
 * @param seqStack 操作的顺序栈
 * @param element  进栈元素
 * @return TRUE | FALSE
 */
int Push(SeqStack *seqStack, StackElementType element) {
    /* 检测栈内是否已经为满栈 */
    if (seqStack->top == MAX_SIZE - 1) {
        /* 栈已满 */
        return FALSE;
    }
    seqStack->top++;
    /* element 进栈 */
    seqStack->elem[seqStack->top] = element;
    return TRUE;
}

/**
 * 出栈操作
 * @param seqStack 操作的顺序栈
 * @param element 出栈元素
 * @return TRUE | FALSE
 */
int Pop(SeqStack *seqStack, StackElementType *element) {
    /* 将 seqStack 栈顶元素弹出,放到 element 所指的存储空间 */
    if (seqStack->top == -1) {
        /* 栈为空 */
        return FALSE;
    } else {
        /* 栈顶元素赋值给 element */
        *element = seqStack->elem[seqStack->top];
        /* 修改栈顶指针 */
        seqStack->top--;
        return TRUE;
    }
}

/**
 * 栈是否为空
 * @param seqStack
 * @return TRUE | FALSE
 */
int IsEmptySeqStack(SeqStack *seqStack) {
    return seqStack->top == -1 ? TRUE : FALSE;
}

/**
 * 获取栈顶元素
 * @param seqStack
 * @param element
 */
void GetSeqStackTopElement(SeqStack *seqStack, StackElementType *element) {
    /* 判断是否为空栈 */
    if (seqStack->top == -1) {
        printf("空栈,栈顶元素为空!");
        element = NULL;
        return;
    }
    /* 获取栈顶元素 */
    *element = seqStack->elem[seqStack->top];
}


/**
 * @param ch1  [
 * @param ch2 ]
 * @return TRUE | FALSE
 */
int Match(char ch1, char ch2) {
    if (ch1 == '(' && ch2 == ')' || ch1 == '[' && ch2 == ']' || ch1 == '{' && ch2 == '}')
        return TRUE;
    else return FALSE;
}

/**
 * 括号匹配
 * @param str 字符串
 */
void BracketMatch(char *str) {
    SeqStack S;
    int i;
    char ch;

    InitStack(&S);

    /* 对字符串中的字符逐一扫描,当输入 0 时终止  */
    for (i = 0; str[i] != '\0'; i++) {
        switch (str[i]) {
            case '(':
            case '[':
            case '{':
                Push(&S, str[i]);
                break;
            case ')':
            case ']':
            case '}':
                /* 判断栈是否为空 */
                if (IsEmptySeqStack(&S)) {
                    /* 输出: 缺少左括号 */
                    printf("%d", missingOpeningParenthesis);
                    return;
                } else {
                    /* 获取栈顶元素 */
                    GetSeqStackTopElement(&S, &ch);
                    /* 用 Match 判断两个括号是否匹配 */
                    if (Match(ch, str[i])) {
                        /* 已经匹配的左括号出栈 */
                        Pop(&S, &ch);
                    } else {
                        /* 输出: 对应的左右括号不匹配 */
                        printf("%d", laRParenthesesDOMatch);
                        return;
                    } /* inner if end */
                } /* out if end */
        } /* switch end */
    } /* for end */

    if (IsEmptySeqStack(&S)) {
        /* 输出: 括号匹配 */
        printf("%d", matchSuccessfully);
    } else {
        /* 输出: 左括号多余 */
        printf("%d", missingClosingParenthesis);
    } /* if end */

}
